package com.ctrip.demo.leetcode;

import java.util.*;

public class LeetCode653 {

    static Set<Integer> set = new HashSet<>();
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5, new TreeNode(3, new TreeNode(2, new TreeNode(), new TreeNode()), new TreeNode()), new TreeNode());
        System.out.println(findTargetByDeque(treeNode, 7));
    }

    public static boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        if (set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }

    public static boolean findTargetByDeque(TreeNode root, int k) {
        // 初始化存放左右两个节点的队列
        Deque<TreeNode> ld = new ArrayDeque<>(), rd = new ArrayDeque<>();
        TreeNode temp = root;
        while (temp != null) {
            ld.addLast(temp);
            temp = temp.left;
        }
        temp = root;
        while (temp != null) {
            rd.addLast(temp);
            temp = temp.right;
        }

        System.out.println("-------");
        TreeNode l = ld.pollLast(), r = rd.pollLast();
        while (l.val < r.val) {
            int t = l.val + r.val;
            if (k == t) {
                return true;
            }
            if (t < k) {
                l = getNext(ld, true);
            }else {
                r = getNext(rd, false);
            }
        }

        return false;
    }

    static TreeNode getNext(Deque<TreeNode> d, boolean isLeft) {
        TreeNode node = isLeft ? d.pollLast().right : d.pollLast().left;
        while (node != null) {
            d.addLast(node);
            node = isLeft ? node.left : node.right;
        }
        return d.peekLast();
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
